The random access memory (RAM) of a computing system is a fixed size resource; currently a RAM size of 32 megabytes (Mb) is typical. The RAM must be managed properly to maintain system performance. In run-time environments such as Java or Microsoft CLI, memory management is handled by the system. Memory management includes a process known as “garbage collection”. Garbage collection is a process with the aim of being as unobtrusive as possible in recycling memory. When a computer program is running it allocates and uses portions of memory on an ongoing basis. At some point the program may no longer need to use a particular portion of memory, e.g., the memory was allocated for a particular purpose that is no longer relevant. The portions that are no longer being used (garbage) are identified (collected) so that they can be reclaimed for future allocation. The garbage collection process taxes the central processing unit (CPU) and degrades system performance as perceived by the application. It is, therefore, highly desirable to reduce the time taken to reclaim unused portions of memory.
Typical computing systems have a cache memory between the CPU and main memory. The cache is small, typically 2 Mb or less, compared to main memory, that is typically 128 Mb. The cache is used to store, and provide fast access to data from the most recently used memory locations. The data is brought to cache with the expectation that it may be accessed again soon. Garbage collection takes place in main memory, but because most programs operate under the assumption that recently accessed data may be accessed again soon, the processing of garbage collection takes place in the cache as described below.
A popular garbage collection algorithm for use in run-time environments is the moving garbage collection algorithm (MGCA). The MGCA examines a memory block that may typically be from 1 Mb to 4 gigabytes (Gb) in size. The MGCA determines which memory data from the block is in use (live data) and which is garbage. As the name implies, MGCAs move all live data to new consecutive memory locations. This compacts the live data into a smaller space than when it was co-located with the garbage. Once the live data is copied to new locations the entire block can be reclaimed and reallocated.
A typical MGCA has three phases: mark, repoint, and copy. In the mark phase the live objects, those to be moved to a new memory location, are determined. At this point new memory locations for the data objects are determined. In the repoint phase the live objects are examined and their references are changed so that they refer to new memory locations. In the copy phase, the contents of each live object are copied to the new memory location.
In many programs when data is accessed, for example to be copied, the data is brought into cache memory. As described above, the cache provides quick access to frequently used memory, and it is assumed that recently accessed data may need to be accessed again soon. If the data is not used again soon it is then deleted from the cache. This process, based on temporal access patterns, frequently results in data being stored to cache only to be deleted when it is not accessed soon. This process taxes the cache memory in determining which data may be deleted from cache and also in having to actually delete it and possibly write back changed data to main memory.
When a live data object is copied to the new memory location, the data copied to the new memory location will not need to be accessed in the future. Therefore, copying the data to the cache in expectation of the data being accessed soon needlessly taxes CPU/cache resources.